//
// Created by PC on 2024-11-1
//
// 查找第一个等于给定值的元素
// 查找最后一个值等于给定值的元素
// 查找第一个大于等于给定值的元素
// 查找第一个大于给定值的元素

/*二分查找变形
 *查找第一个/ 最后一个值等于给定值的元素
 * OJ: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *查找第一个/ 最后一个值大于等于给定值的元素
 *
 * 讲解:  http://t.csdnimg.cn/uspHf
 * https://www.cnblogs.com/sunshuyi/p/12681088.html
 * */

#include <iostream>
#include <vector>

using namespace std;

// 查找第一个等于给定值的元素的下标
int searchFirst(vector<int> &vv, int x)
{
    return -1;
}

// 查找列表中最后一个等于给定值的元素的下标
int searchLast(vector<int> &vv, int target)
{
    int l = 0, r = vv.size() - 1;
    if (target<vv[l] || target>vv[r])
        return -1;
    int m,t=-1;
    while(l<=r)
    {
        m = r+(l-r)/2;
        if(vv[m]==target)
        {
            t=m;
            l=m+1;
        }
        else if(target>vv[m])
            l=m+1;
        else
            r=m-1;
    }
    return t;
}

// 查找第一个大于等于给定值的元素的下标
int searchFirstLargeEqual(vector<int> &vv, int target)
{
    if (target > vv[vv.size() - 1])
        return -1;
    int l = 0, r = vv.size() - 1;
    int t = r;
    int m;
    while (l <= r)
    {
//        m = (r + l) / 2;
        m = r+(l-r)/2;
        if (vv[m] < target)
        {
            l = m + 1;
        } else
        {
            t = m;
            r = m - 1;
        }

    }
    return t;
}

// 查找最后一个小于等于给定值的元素的下标
int searchLastEqualLess(vector<int> &vv, int target)
{
    int l=0,r=vv.size()-1;
    if(vv[r]<target)
        return r;
    if(vv[l]>target)
        return -1;
    int m,t=-1;
    while(l<=r)
    {
        m=l+(r-l)/2;
        if(vv[m]<=target)
        {
            t=m;
            l=m+1;
        }
        else
            r=m-1;
    }
    return t;
}

int main()
{
    //                0   1  2  3  4  5  6  7  8  9  10 11 12
    vector<int> l = {-11, 0, 0, 1, 1, 1, 2, 2, 3, 5, 7, 9, 9};
//    cout << searchFirst(l, 10) << endl;
//    cout << searchLast(l, 3) << endl;
    // 查找第一个大于等于给定值的元素
//    cout << searchFirstLargeEqual(l, 1) << endl;
// 查找最后一个小于等于给定值的元素的下标
    cout << searchLastEqualLess(l, 3) << endl;
    return 0;
}